<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="utf-8">
  
  <title>Djstra最短路径 | 探花需拔根</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  
    <meta name="keywords" content="Bluarry,bluarry,Blog,探花,拔根,博客,区块链,算法,acm">
  
  <meta name="description" content="简介: 数据结构学习笔记">
<meta name="keywords" content="最短路径">
<meta property="og:type" content="article">
<meta property="og:title" content="Djstra最短路径">
<meta property="og:url" content="/2016/11/28/Djstra最短路径/index.html">
<meta property="og:site_name" content="探花需拔根">
<meta property="og:description" content="简介: 数据结构学习笔记">
<meta property="og:locale" content="zh.yml">
<meta property="og:image" content="/img/uploads/2016/11/2016110.png">
<meta property="og:image" content="/2016/11/28/Djstra最短路径/index.html#">
<meta property="og:updated_time" content="2020-06-19T12:58:16.000Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Djstra最短路径">
<meta name="twitter:description" content="简介: 数据结构学习笔记">
<meta name="twitter:image" content="/img/uploads/2016/11/2016110.png">
  
  
    <link rel="icon" href="/favicon.ico">
  
  <link href="//cdn.bootcss.com/font-awesome/4.7.0/css/font-awesome.min.css" rel="stylesheet" type="text/css">
  <link rel="stylesheet" href="/css/style.css">
  <script src="/js/pace.min.js"></script>
  

  
  

  
<!-- Matomo -->
<script type="text/javascript">
	var _paq = window._paq || [];
	/* tracker methods like "setCustomDimension" should be called before "trackPageView" */
	_paq.push(['trackPageView']);
	_paq.push(['enableLinkTracking']);
	(function() {
	  var u="//matomo.bluarry.top/";
	  _paq.push(['setTrackerUrl', u+'matomo.php']);
	  _paq.push(['setSiteId', '3']);
	  var d=document, g=d.createElement('script'), s=d.getElementsByTagName('script')[0];
	  g.type='text/javascript'; g.async=true; g.defer=true; g.src=u+'matomo.js'; s.parentNode.insertBefore(g,s);
	})();
  </script>
  <!-- End Matomo Code -->

</head>
</html>
<body>
  <div id="container">
      <header id="header">
    <div id="banner"></div>
    <div id="header-outer">
        <div id="header-menu" class="header-menu-pos animated">
            <div class="header-menu-container">
                <a href="/" class="left">
                    <span class="site-title">探花需拔根</span>
                </a>
                <nav id="header-menu-nav" class="right">
                    
                    <a  href="/">
                        <i class="fa fa-home"></i>
                        <span>主页</span>
                    </a>
                    
                    <a  href="/archives">
                        <i class="fa fa-archive"></i>
                        <span>归档</span>
                    </a>
                    
                    <a  href="/friends">
                        <i class="fa fa-envira"></i>
                        <span>友链</span>
                    </a>
                    
                    <a  href="/about">
                        <i class="fa fa-user"></i>
                        <span>关于我</span>
                    </a>
                    
                </nav>
                <a class="mobile-header-menu-button">
                    <i class="fa fa-bars"></i>
                </a>
            </div>
        </div>
        <div id="header-row">
            <div id="logo">
                <a href="/">
                    <img src="/images/avatar/me-130x130.jpg" alt="logo">
                </a>
            </div>
            <div class="header-info">
                <div id="header-title">
                    
                    <h2>
                        清风觅影
                    </h2>
                    
                </div>
                <div id="header-description">
                    
                    <h3>
                        致需极,守静笃
                    </h3>
                    
                </div>
            </div>
            <nav class="header-nav">
                <div class="social">
                    
                        <a title="Home"  href="/">
                            <i class="fa fa-home fa-2x"></i></a>
                    
                        <a title="Github" target="_blank" href="//github.com/bluarry">
                            <i class="fa fa-github fa-2x"></i></a>
                    
                        <a title="mail" target="_blank" href="mailto://bluarry@qq.com">
                            <i class="fa fa-envelope-o fa-2x"></i></a>
                    
                </div>
            </nav>
        </div>
    </div>
</header>
      <div class="outer">
        <section id="main" class="body-wrap"><article id="post-Djstra最短路径" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-inner">
    
      <header class="article-header">
        
  
    <h1 class="post-title" itemprop="name">
      Djstra最短路径
    </h1>
    <div class="post-title-bar">
      <ul>
          
              <li>
                  <i class="fa fa-book"></i>
                  
                      <a href="/categories/数据结构/">数据结构</a>
                  
              </li>
          
        <li>
          <i class="fa fa-calendar"></i>  2016-11-28
        </li>
        <li>
          <i class="fa fa-eye"></i>
          <span id="busuanzi_value_page_pv"></span>
        </li>
      </ul>
    </div>
  

          
      </header>
    
    <div class="article-entry post-content" itemprop="articleBody">
      
            
            <blockquote>
<p>简介: 数据结构学习笔记<br><a id="more"></a></p>
<h1 id="Djstra最短路径"><a href="#Djstra最短路径" class="headerlink" title="Djstra最短路径"></a>Djstra最短路径</h1><p><img src="/img/uploads/2016/11/2016110.png" alt></p>
<h2 id="希望看这篇文章的人都能懂"><a href="#希望看这篇文章的人都能懂" class="headerlink" title="希望看这篇文章的人都能懂"></a>希望看这篇文章的人都能懂</h2><p><b><strong>图的最短路径问题——克鲁斯卡尔算法</strong></b></p>
<p>算法的思想为：将所有的点分为两类:<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;S：已求出最短路径的顶点的集合&lt;/ br&gt;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;V-S=T：尚未确定最短路径的顶点集合<br></p>
</blockquote>
<h2 id="求最短路径步骤为："><a href="#求最短路径步骤为：" class="headerlink" title="求最短路径步骤为："></a><b>求最短路径步骤为：</b></h2><p><img src="#" alt="图示案例"></p>
<blockquote>
<p>1.初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值， 若存在<v0,vi>，为<v0,vi>弧上的权值（和ＳＰＦＡ初始化方式不同），&lt;/br&gt;<br>若不存在<v0,vi>，为Inf。<br>2.从T中选取一个其距离值为最小的顶点W(贪心体现在此处)，加入S(注意不是直接从S集合中选取，理解这个对于理解dist数组的作用至关重要)&lt;/br&gt;，对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值&lt;/br&gt;（上面两个并列for循环，使用最小点更新）。<br>3.重复上述步骤，直到S中包含所有顶点，即S=V为止（说明最外层是除起点外的遍历）。</v0,vi></v0,vi></v0,vi></p>
</blockquote>
<h2 id="自己的理解"><a href="#自己的理解" class="headerlink" title="自己的理解"></a>自己的理解</h2><blockquote>
<p>我认为以上说法已经很清楚了，这里不再赘述</p>
</blockquote>
<h2 id="我的代码如下"><a href="#我的代码如下" class="headerlink" title="我的代码如下"></a>我的代码如下</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;string&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stack&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> INIFITY 32767</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX_VERTEX_NUM 1000</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> adjtype;</span><br><span class="line"><span class="keyword">typedef</span> <span class="built_in">string</span> vextype;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>&#123;</span></span><br><span class="line">    vextype *vex;<span class="comment">//顶点信息</span></span><br><span class="line">    adjtype **adj;<span class="comment">//边的权值</span></span><br><span class="line">    <span class="keyword">int</span> vetexnum,adjnum;</span><br><span class="line">&#125;Graph;</span><br><span class="line"></span><br><span class="line"><span class="comment">//求a节点的下标</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">locate</span><span class="params">(Graph G,vextype a)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(;i&lt;G.vetexnum;i++) <span class="keyword">if</span>(G.vex[i]==a) <span class="keyword">return</span> i;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//创建有向图</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">CreatGraph</span><span class="params">(Graph&amp; G)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"请依次输入有向图顶点数目，边的数目 ："</span> &lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">    <span class="built_in">cin</span> &gt;&gt; G.vetexnum &gt;&gt; G.adjnum;</span><br><span class="line">    G.vex=<span class="keyword">new</span> vextype[G.vetexnum];</span><br><span class="line">    <span class="keyword">if</span>(!G.vex) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"分别输入结点的信息： "</span>&lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;G.vetexnum;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">cin</span> &gt;&gt; G.vex[i];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"请分别输入边以及权重 ： "</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line"></span><br><span class="line">     G.adj=<span class="keyword">new</span> adjtype* [G.vetexnum];   <span class="comment">//new 一个二维数组</span></span><br><span class="line">     <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;G.vetexnum;i++)</span><br><span class="line">         G.adj[i]= <span class="keyword">new</span> adjtype[G.vetexnum];</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span>(!G.adj) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;G.vetexnum;i++)</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;G.vetexnum;j++)</span><br><span class="line">        &#123;</span><br><span class="line">            G.adj[i][j]=INIFITY;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">    vextype a,b;</span><br><span class="line">       <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;G.adjnum;i++)</span><br><span class="line">       &#123;</span><br><span class="line">           <span class="keyword">int</span> weight;</span><br><span class="line">            <span class="built_in">cin</span> &gt;&gt; a &gt;&gt; b &gt;&gt; weight;</span><br><span class="line">            <span class="keyword">int</span> x=locate(G,a);</span><br><span class="line">            <span class="keyword">int</span> y=locate(G,b);</span><br><span class="line">            <span class="keyword">if</span>(x==<span class="number">-1</span> || y==<span class="number">-1</span>)</span><br><span class="line">            &#123;</span><br><span class="line">               <span class="built_in">cout</span> &lt;&lt; <span class="string">"输入的边有误"</span>;</span><br><span class="line">                <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            G.adj[x][y]=weight;</span><br><span class="line">       &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Road_print</span><span class="params">(Graph G,<span class="keyword">int</span> *pre,<span class="keyword">int</span> x,<span class="keyword">int</span> v0,<span class="keyword">int</span> *dist)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> y=x;</span><br><span class="line">    <span class="keyword">if</span>(x==v0) <span class="keyword">return</span> ;</span><br><span class="line">    <span class="built_in">stack</span>&lt;<span class="keyword">int</span>&gt; s;</span><br><span class="line">    s.push(x);</span><br><span class="line">    <span class="keyword">for</span>(;pre[x]!=<span class="number">-1</span>;x=pre[x])</span><br><span class="line">    &#123;</span><br><span class="line">        s.push(pre[x]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(x!=v0)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">cout</span>&lt;&lt;G.vex[v0] &lt;&lt; <span class="string">"到 "</span> &lt;&lt; G.vex[y] &lt;&lt; <span class="string">" 无路径"</span>&lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt;G.vex[v0] &lt;&lt; <span class="string">"到 "</span> &lt;&lt; G.vex[y] &lt;&lt; <span class="string">" 的路径为 : "</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span>(!s.empty())</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">cout</span> &lt;&lt; G.vex[s.top()] &lt;&lt; <span class="string">" "</span>;</span><br><span class="line">        s.pop();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"\n最短路径长度为 :"</span> &lt;&lt; dist[y];</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Djstra</span><span class="params">(Graph G,<span class="keyword">int</span> v0)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> dist[G.vetexnum];</span><br><span class="line">    <span class="keyword">int</span> pre[G.vetexnum];</span><br><span class="line">    <span class="keyword">bool</span> S[G.vetexnum];</span><br><span class="line"></span><br><span class="line">    <span class="comment">//初始化dist为V0的邻接点</span></span><br><span class="line">    <span class="comment">//将集合S置为空，并将前驱设置为v0</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;G.vetexnum;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        dist[i] = G.adj[v0][i];</span><br><span class="line">        S[i] = <span class="literal">false</span>;</span><br><span class="line">        <span class="keyword">if</span>(dist[i] == INIFITY)</span><br><span class="line">           pre[i] = <span class="number">-1</span>;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">           pre[i] = v0;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    dist[v0]=<span class="number">0</span>;</span><br><span class="line">    S[v0]=<span class="literal">true</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>; i&lt;G.vetexnum; i++)</span><br><span class="line">        &#123;</span><br><span class="line">             <span class="keyword">int</span> mindist = INIFITY;         <span class="comment">//最小的元素</span></span><br><span class="line">             <span class="keyword">int</span> u = v0;                    <span class="comment">//记录dist中不是S集合最小元素的下标</span></span><br><span class="line">             <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>; j&lt;G.vetexnum; ++j)</span><br><span class="line">                <span class="keyword">if</span>((!S[j]) &amp;&amp; dist[j]&lt;mindist)</span><br><span class="line">                &#123;</span><br><span class="line">                      u = j;</span><br><span class="line">                     mindist = dist[j];</span><br><span class="line">                &#125;</span><br><span class="line">             S[u] = <span class="literal">true</span>;</span><br><span class="line">             <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>; j&lt;G.vetexnum; j++)</span><br><span class="line">                 <span class="keyword">if</span>((!S[j]) &amp;&amp; (dist[u] + G.adj[u][j] &lt; dist[j]))</span><br><span class="line">                 &#123;</span><br><span class="line">                         dist[j] = dist[u] + G.adj[u][j];</span><br><span class="line">                         pre[j] = u;</span><br><span class="line">                  &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;G.vetexnum;i++)</span><br><span class="line">        Road_print(G,pre,i,v0,dist);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    freopen(<span class="string">"./in"</span>,<span class="string">"r"</span>,<span class="built_in">stdin</span>);</span><br><span class="line">    Graph G;</span><br><span class="line">    <span class="keyword">if</span>(!CreatGraph(G))</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">cout</span> &lt;&lt; <span class="string">"创建图失败！"</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"请输入起始节点 :\n"</span>;</span><br><span class="line">    vextype x;</span><br><span class="line">    <span class="built_in">cin</span> &gt;&gt; x;</span><br><span class="line">    Djstra(G,locate(G,x));</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

            <div class="post-copyright">
    <div class="content">
        <p>最后更新： 2020年06月19日 20:58</p>
        <p>原始链接： <a class="post-url" href="/2016/11/28/Djstra最短路径/" title="Djstra最短路径">/2016/11/28/Djstra最短路径/</a></p>
        <footer>
            <a href="">
                <img src="/images/avatar/me-130x130.jpg" alt="bluarry">
                bluarry
            </a>
        </footer>
    </div>
</div>

      
        
            
<div class="page-reward">
    <a id="rewardBtn" href="javascript:;">赏</a>
</div>

<div id="reward" class="post-modal reward-lay">
    <a class="close" href="javascript:;" id="reward-close">×</a>
    <span class="reward-title">
        <i class="icon icon-quote-left"></i>
        请我吃糖~
        <i class="icon icon-quote-right"></i>
    </span>
    <div class="reward-content">
        
        <div class="reward-code">
            <img id="rewardCode" src="/images/wechat_code.jpg" alt="打赏二维码">
        </div>
        <div class="reward-select">
            
            <label class="reward-select-item checked" data-id="wechat" data-wechat="/images/wechat_code.jpg">
                <img class="reward-select-item-wechat" src="/images/wechat.png" alt="微信">
            </label>
            
            
            <label class="reward-select-item" data-id="alipay" data-alipay="/images/alipay_code.jpg">
                <img class="reward-select-item-alipay" src="/images/alipay.png" alt="支付宝">
            </label>
            
        </div>
    </div>
</div>


        
    </div>
    <footer class="article-footer">
        
        
<div class="post-share">
    <a href="javascript:;" id="share-sub" class="post-share-fab">
        <i class="fa fa-share-alt"></i>
    </a>
    <div class="post-share-list" id="share-list">
        <ul class="share-icons">
          <li>
            <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=/2016/11/28/Djstra最短路径/&title=《Djstra最短路径》 — 探花需拔根&pic=images/avatar/me-130x130.jpg" data-title="微博">
              <i class="fa fa-weibo"></i>
            </a>
          </li>
          <li>
            <a class="weixin share-sns" id="wxFab" href="javascript:;" data-title="微信">
              <i class="fa fa-weixin"></i>
            </a>
          </li>
          <li>
            <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=/2016/11/28/Djstra最短路径/&title=《Djstra最短路径》 — 探花需拔根&source=
简介: 数据结构学习笔记" data-title="QQ">
              <i class="fa fa-qq"></i>
            </a>
          </li>
          <li>
            <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=/2016/11/28/Djstra最短路径/" data-title="Facebook">
              <i class="fa fa-facebook"></i>
            </a>
          </li>
          <li>
            <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《Djstra最短路径》 — 探花需拔根&url=/2016/11/28/Djstra最短路径/&via=" data-title="Twitter">
              <i class="fa fa-twitter"></i>
            </a>
          </li>
          <li>
            <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=/2016/11/28/Djstra最短路径/" data-title="Google+">
              <i class="fa fa-google-plus"></i>
            </a>
          </li>
        </ul>
     </div>
</div>
<div class="post-modal wx-share" id="wxShare">
    <a class="close" href="javascript:;" id="wxShare-close">×</a>
    <p>扫一扫，分享到微信</p>
    <img src="" alt="微信分享二维码">
</div>

<div class="mask"></div>

        
        <ul class="article-footer-menu">
            
            
  <li class="article-footer-tags">
    <i class="fa fa-tags"></i>
      
    <a href="/tags/最短路径/" class="color5">最短路径</a>
      
  </li>

        </ul>
        
        

    <aside class="post-toc-pos post-toc-top" id="post-toc">
        <nav class="post-toc-wrap">
            <ol class="post-toc"><li class="post-toc-item post-toc-level-1"><a class="post-toc-link" href="#Djstra最短路径"><span class="post-toc-text">Djstra最短路径</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#希望看这篇文章的人都能懂"><span class="post-toc-text">希望看这篇文章的人都能懂</span></a></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#求最短路径步骤为："><span class="post-toc-text">求最短路径步骤为：</span></a></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#自己的理解"><span class="post-toc-text">自己的理解</span></a></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#我的代码如下"><span class="post-toc-text">我的代码如下</span></a></li></ol></li></ol>
        </nav>
    </aside>
    

<nav id="article-nav">
  
    <a href="/2017/01/25/kalilinux安装ss-qt5/" id="article-nav-newer" class="article-nav-link-wrap">

      <span class="article-nav-title">
        <i class="fa fa-hand-o-left" aria-hidden="true"></i>
        
          Kali Linux 下安装 ss-qt5
        
      </span>
    </a>
  
  
    <a href="/2016/11/28/图的最小生成树——克鲁斯卡尔算法/" id="article-nav-older" class="article-nav-link-wrap">
      <span class="article-nav-title">图的最小生成树——克鲁斯卡尔算法</span>
      <i class="fa fa-hand-o-right" aria-hidden="true"></i>
    </a>
  
</nav>




    <!-- HTML页面布局 -->
    <div id="tab-list">
        <ul id="ul1">
            
            
            
            <li id="gittalk" style="width: 25%;">gittalk</li>
            
            
            <li id="valine" style="width: 25%;">valine</li>
            
        </ul>
         
        
          
        <div id="dv_gitment" class="hide">
            <div id="git_comments"></div>;
        </div>
        
        
        <div id="dv_vment" class="show">
            <div class="comments vcomment" id="vcomments"></div>
        </div>
        
    </div>

    <script src="/js/tablist.js"></script>
   

    
        
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.css">
<script src="https://cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.min.js"></script>
<script src="https://cdn.bluarry.top/cdn/js/md5.min.js"></script>
<!--<div id="git_comments"></div>-->
<script>
    // var gitment = new Gitment({
    //     owner: 'bluarry',
    //     repo: 'blog_comment',
    //     oauth: {
    //         client_id: '5c95f5b820d109c8f5c1',
    //         client_secret: 'f1cfe5b08f9a55923ba26a9ec8855b631002ad18',
    //     },
    // })
    var hrefs=location.href;
    var links=hrefs.split('/');
    var cr="";
    for (var i=0;i<Math.min(7,links.length);i++) {
        cr+=links[i];
    }
    console.log(cr);

    var gitalk = new Gitalk({
        clientID: '5c95f5b820d109c8f5c1', //Client ID
        clientSecret: 'f1cfe5b08f9a55923ba26a9ec8855b631002ad18', //Client Secret
        repo: 'blog_comment',//仓库名称
        owner: 'bluarry',//仓库拥有者
        admin: ['bluarry'],
        id: md5(cr),      // Ensure uniqueness and length less than 50
        distractionFreeMode: false  // Facebook-like distraction free mode
    });
    gitalk.render('git_comments');
</script>


    
        <!-- Valine Comments -->
<!-- <div class="comments vcomment" id="vcomments"></div>-->
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src="//unpkg.com/valine@latest/dist/Valine.min.js"></script>
<!-- Valine Comments script -->
<script>
    var GUEST_INFO = ['nick','mail','link'];
    var guest_info = 'nick,mail'.split(',').filter(function(item){
        return GUEST_INFO.indexOf(item) > -1
    });
    new Valine({
        el: '#vcomments',
        notify: 'true' == 'true',
        verify: 'false' == 'true',
        appId: "DRrkhLYTmB6QwGy6sI6vCH8C-gzGzoHsz",
        appKey: "M4A4lrKwbixQmmeO5lVdY5l2",
        avatar: "mm",
        placeholder: "少侠，留下你的评论吧",
        guest_info: guest_info.length == 0 ? GUEST_INFO : guest_info,
        pageSize: "10"
    })
</script>
<!-- Valine Comments end -->

    


    </footer>
  </div>
</article>


</section>
        
      </div>
      <footer id="footer">
  <div class="outer">
    <div id="footer-info" class="inner">
      
<p>
    <span id="busuanzi_container_site_uv" style='display:none'>
        <i class="fa fa-user"></i>&nbsp;&nbsp;<span id="busuanzi_value_site_uv"></span>
    </span>&nbsp;&nbsp;|&nbsp;&nbsp;
    <span id="busuanzi_container_site_pv" style='display:none'>
        <i class="fa fa-eye"></i> &nbsp;&nbsp;<span id="busuanzi_value_site_pv"></span>
    </span>
</p>


      <p>
      &copy; 2016-2021 &nbsp;&nbsp;<i style="color: red;" class="fa fa-heart"></i>&nbsp;&nbsp; bluarry
      备案号: <a style="color: #999;" href="http://www.beian.miit.gov.cn/" target="_blank">陕ICP备2020012959号</a>
    </p>

    </div>
  </div>
</footer>
    <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
<script src="//cdn.bootcss.com/jquery/3.2.1/jquery.min.js"></script>
<script>
  var mihoConfig = {
      root: "",
      animate: true,
      isHome: false,
      share: true,
      reward: 1
  }
</script>
<div class="sidebar">
    <div id="sidebar-search" title="Search">
        <i class="fa fa-search"></i>
    </div>
    <div id="sidebar-category" title="Categories">
        <i class="fa fa-book"></i>
    </div>
    <div id="sidebar-tag" title="Tags">
        <i class="fa fa-tags"></i>
    </div>
    <div id="sidebar-top">
        <span class="sidebar-top-icon"><i class="fa fa-angle-up"></i></span>
    </div>
</div>
<div class="sidebar-menu-box" id="sidebar-menu-box">
    <div class="sidebar-menu-box-container">
        <div id="sidebar-menu-box-categories">
            <a class="category-link" href="/categories/linux/">linux</a><a class="category-link" href="/categories/linux-学习/">linux 学习</a><a class="category-link" href="/categories/linux-学习-acm-onlinejudge-hustoj/">linux 学习 acm onlinejudge hustoj</a><a class="category-link" href="/categories/学习分享/">学习分享</a><a class="category-link" href="/categories/数据结构/">数据结构</a><a class="category-link" href="/categories/经验分享/">经验分享</a><a class="category-link" href="/categories/经验分享/学习分享/">学习分享</a><a class="category-link" href="/categories/默认分类/">默认分类</a><a class="category-link" href="/categories/默认分类/复习/">复习</a><a class="category-link" href="/categories/默认分类/复习/学习分享/">学习分享</a><a class="category-link" href="/categories/默认分类/学习分享/">学习分享</a><a class="category-link" href="/categories/默认分类/生活杂谈/">生活杂谈</a><a class="category-link" href="/categories/默认分类/经验分享/">经验分享</a><a class="category-link" href="/categories/默认分类/经验分享/学习分享/">学习分享</a>
        </div>
        <div id="sidebar-menu-box-tags">
            <a href="/tags/Java/" style="font-size: 10px;">Java</a> <a href="/tags/acm/" style="font-size: 12.86px;">acm</a> <a href="/tags/android/" style="font-size: 11.43px;">android</a> <a href="/tags/c/" style="font-size: 14.29px;">c++</a> <a href="/tags/fabric/" style="font-size: 11.43px;">fabric</a> <a href="/tags/kali/" style="font-size: 10px;">kali</a> <a href="/tags/linux/" style="font-size: 15.71px;">linux</a> <a href="/tags/linux学习/" style="font-size: 10px;">linux学习</a> <a href="/tags/mac/" style="font-size: 10px;">mac</a> <a href="/tags/mfc/" style="font-size: 10px;">mfc</a> <a href="/tags/onlinejudge/" style="font-size: 10px;">onlinejudge</a> <a href="/tags/sqlite/" style="font-size: 10px;">sqlite</a> <a href="/tags/sqlite3/" style="font-size: 11.43px;">sqlite3</a> <a href="/tags/ss/" style="font-size: 10px;">ss</a> <a href="/tags/vs/" style="font-size: 11.43px;">vs</a> <a href="/tags/xposed/" style="font-size: 10px;">xposed</a> <a href="/tags/xposed模块/" style="font-size: 10px;">xposed模块</a> <a href="/tags/专业知识/" style="font-size: 10px;">专业知识</a> <a href="/tags/侧链/" style="font-size: 10px;">侧链</a> <a href="/tags/内网穿透/" style="font-size: 10px;">内网穿透</a> <a href="/tags/区块链/" style="font-size: 11.43px;">区块链</a> <a href="/tags/复习/" style="font-size: 10px;">复习</a> <a href="/tags/学习/" style="font-size: 18.57px;">学习</a> <a href="/tags/安卓/" style="font-size: 12.86px;">安卓</a> <a href="/tags/小技巧/" style="font-size: 17.14px;">小技巧</a> <a href="/tags/数据库/" style="font-size: 10px;">数据库</a> <a href="/tags/数据结构/" style="font-size: 10px;">数据结构</a> <a href="/tags/日常使用问题/" style="font-size: 10px;">日常使用问题</a> <a href="/tags/最小生成树/" style="font-size: 11.43px;">最小生成树</a> <a href="/tags/最短路径/" style="font-size: 10px;">最短路径</a> <a href="/tags/比特币/" style="font-size: 11.43px;">比特币</a> <a href="/tags/算法/" style="font-size: 12.86px;">算法</a> <a href="/tags/算法笔记/" style="font-size: 11.43px;">算法笔记</a> <a href="/tags/经验/" style="font-size: 20px;">经验</a> <a href="/tags/编译原理/" style="font-size: 10px;">编译原理</a> <a href="/tags/翻译/" style="font-size: 10px;">翻译</a> <a href="/tags/自然计算/" style="font-size: 10px;">自然计算</a>
        </div>
    </div>
    <a href="javascript:;" class="sidebar-menu-box-close">&times;</a>
</div>
<div class="mobile-header-menu-nav" id="mobile-header-menu-nav">
    <div class="mobile-header-menu-container">
        <span class="title">Menus</span>
        <ul class="mobile-header-menu-navbar">
            
            <li>
                <a  href="/">
                    <i class="fa fa-home"></i><span>主页</span>
                </a>
            </li>
            
            <li>
                <a  href="/archives">
                    <i class="fa fa-archive"></i><span>归档</span>
                </a>
            </li>
            
            <li>
                <a  href="/friends">
                    <i class="fa fa-envira"></i><span>友链</span>
                </a>
            </li>
            
            <li>
                <a  href="/about">
                    <i class="fa fa-user"></i><span>关于我</span>
                </a>
            </li>
            
        </ul>
    </div>
    <div class="mobile-header-tag-container">
        <span class="title">Tags</span>
        <div id="mobile-header-container-tags">
            <a href="/tags/Java/" style="font-size: 10px;">Java</a> <a href="/tags/acm/" style="font-size: 12.86px;">acm</a> <a href="/tags/android/" style="font-size: 11.43px;">android</a> <a href="/tags/c/" style="font-size: 14.29px;">c++</a> <a href="/tags/fabric/" style="font-size: 11.43px;">fabric</a> <a href="/tags/kali/" style="font-size: 10px;">kali</a> <a href="/tags/linux/" style="font-size: 15.71px;">linux</a> <a href="/tags/linux学习/" style="font-size: 10px;">linux学习</a> <a href="/tags/mac/" style="font-size: 10px;">mac</a> <a href="/tags/mfc/" style="font-size: 10px;">mfc</a> <a href="/tags/onlinejudge/" style="font-size: 10px;">onlinejudge</a> <a href="/tags/sqlite/" style="font-size: 10px;">sqlite</a> <a href="/tags/sqlite3/" style="font-size: 11.43px;">sqlite3</a> <a href="/tags/ss/" style="font-size: 10px;">ss</a> <a href="/tags/vs/" style="font-size: 11.43px;">vs</a> <a href="/tags/xposed/" style="font-size: 10px;">xposed</a> <a href="/tags/xposed模块/" style="font-size: 10px;">xposed模块</a> <a href="/tags/专业知识/" style="font-size: 10px;">专业知识</a> <a href="/tags/侧链/" style="font-size: 10px;">侧链</a> <a href="/tags/内网穿透/" style="font-size: 10px;">内网穿透</a> <a href="/tags/区块链/" style="font-size: 11.43px;">区块链</a> <a href="/tags/复习/" style="font-size: 10px;">复习</a> <a href="/tags/学习/" style="font-size: 18.57px;">学习</a> <a href="/tags/安卓/" style="font-size: 12.86px;">安卓</a> <a href="/tags/小技巧/" style="font-size: 17.14px;">小技巧</a> <a href="/tags/数据库/" style="font-size: 10px;">数据库</a> <a href="/tags/数据结构/" style="font-size: 10px;">数据结构</a> <a href="/tags/日常使用问题/" style="font-size: 10px;">日常使用问题</a> <a href="/tags/最小生成树/" style="font-size: 11.43px;">最小生成树</a> <a href="/tags/最短路径/" style="font-size: 10px;">最短路径</a> <a href="/tags/比特币/" style="font-size: 11.43px;">比特币</a> <a href="/tags/算法/" style="font-size: 12.86px;">算法</a> <a href="/tags/算法笔记/" style="font-size: 11.43px;">算法笔记</a> <a href="/tags/经验/" style="font-size: 20px;">经验</a> <a href="/tags/编译原理/" style="font-size: 10px;">编译原理</a> <a href="/tags/翻译/" style="font-size: 10px;">翻译</a> <a href="/tags/自然计算/" style="font-size: 10px;">自然计算</a>
        </div>
    </div>
</div>
<div class="search-wrap">
    <span class="search-close">&times;</span>
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="back">
            <i class="icon icon-lg icon-chevron-left"></i>
        </a>
        <input class="search-field" placeholder="Search..." id="keywords">
        <a id="search-submit" href="javascript:;">
            <i class="fa fa-search"></i>
        </a>
    <div class="search-container" id="search-container">
        <ul class="search-result" id="search-result">
        </ul>
    </div>
</div>

<div id="search-tpl">
    <li class="search-result-item">
        <a href="{url}" class="search-item-li">
            <span class="search-item-li-title" title="{title}">{title}</span>
        </a>
    </li>
</div>
<script src="/js/search.js"></script>
<script src="/js/main.js"></script>


  <script src="//cdn.bootcss.com/particles.js/2.0.0/particles.min.js"></script>
  <div id="particles"></div>
  <script src="/js/particles.js"></script>







  <link rel="stylesheet" href="//cdn.bootcss.com/animate.css/3.5.0/animate.min.css">
  <script src="//cdn.bootcss.com/scrollReveal.js/3.0.5/scrollreveal.js"></script>
  <script src="/js/animate.js"></script>


  <script src="/js/pop-img.js"></script>
  <script>
     $(".article-entry p img").popImg();
  </script>

  </div>
</body>
</html>